/**
 * Interleaving String
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
 */
package com.xinpan.exercise;

//do again
public class InterleavingString {
    public boolean isInterleave(String s1, String s2, String s3) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s3.length() == 0)
        {
            if(s1.length() != 0 || s2.length() != 0)
                return false;
            else
                return true;
        }
        if(s1.length() == 0)
            return s2.equals(s3);
        if(s2.length() == 0)
            return s1.equals(s3);
        if(s3.length() != s1.length()+s2.length())
            return false;
    
        boolean[][] dp = new boolean[s1.length()+1][s2.length()+1];
        dp[0][0] = true;
        for(int i = 0; i < s1.length(); i++)
            if(s3.charAt(i) == s1.charAt(i))
                dp[i+1][0] = true;
            else
                dp[i+1][0] = false;
        
        for(int j = 0; j < s2.length(); j++)
            if(s3.charAt(j) == s2.charAt(j))
                dp[0][j+1] = true;
            else
                dp[0][j+1] = false;
        
        for(int i = 0; i < s1.length(); i++)
        {
            for(int j = 0; j < s2.length(); j++)
            {
                if(dp[i+1][j] && s2.charAt(j) == s3.charAt(i+j+1) ||
                    dp[i][j+1] && s1.charAt(i) == s3.charAt(i+j+1))
                    dp[i+1][j+1] = true;
                else
                    dp[i+1][j+1] = false;
            }
        }   
        return dp[s1.length()][s2.length()];
    }
	   
	   public static void main(String[] args)
	   {
		   InterleavingString is = new InterleavingString();
		   is.isInterleave("aabaac", "aadaaeaaf", "aadaaeaabaafaac");
	   }
}

